To strengthen the security of computer systems against network intrusions and server compromises, key splitting is often applied in order to split a secret state (typically a key) of a system into a number of “partial states,” or shares (typically, randomly chosen), which are then dispersed into a number of parties, or share holders (typically, computing devices). Then, the task of an attacker is much harder: Leakage of the full secret state requires that the attacker gets access to a sufficiently large number of the shares.
However, any key splitting method is eventually prone to compromise of the full secret state of the system if the attacker is launching a perpetual attack where devices or servers that hold the shares are gradually compromised until a large enough number of shares are possessed by the attacker to successfully reconstruct the split secret state. Therefore, it is often desirable for key splitting to be complemented by a proactivization mechanism that refreshes the current set of shares, or sharing, into a new set of shares, often referred to as a new sharing. In this manner, new shares can be used to reconstruct the same split key, yet they are uncorrelated with the old shares. That is, the current share(s) that an attacker possesses become useless once a new sharing replaces the current sharing.
Many efficient proactivization techniques exist for various secret sharing schemes. In particular, Amir Herzberg et al., “Proactive Secret Sharing or: How to Cope with Perpetual Leakage,” Advances in Cryptology—CRYPTO '95, Proc. 15th Annual Int'l Cryptology Conf., 339-352 (Aug. 27-31, 1995) shows an efficient proactivization of Shamir's sharing scheme (see, e.g., A. Shamir, “How to Share a Secret,” Communications of the Ass'n of Computer Machinery, Vol. 22, No. 11, 612-13 (1979)), in a distributed manner so that share holders can jointly compute random correction shares that, when individually combined with the current shares, can produce refreshed, new shares. Notably, this joint computation remains secure even if one or more (but up to a threshold value) of the participating share holders are compromised by an attacker.
U.S. patent application Ser. No. 14/672,507, filed Mar. 30, 2015, entitled “Methods and Apparatus for Password-Based Secret Sharing Scheme,” incorporated by reference herein, discloses a password-based secret sharing (PBSS) mechanism (for threshold and generic secret sharing). PBSS allows for one or more of the shares to be fixed, that is, to take predetermined values that are independent of the split secret (e.g., independent of the shared key), and thus are not necessarily randomly chosen. U.S. patent application Ser. No. 14/577,206, filed Dec. 19, 2014, entitled “Protection of a Secret on a Mobile Device Using a Secret-Splitting Technique with a Fixed User Share,” (now U.S. Pat. No. 9,455,968), incorporated by reference herein, discloses a key-splitting framework where the key splitting employs a user's password or other personal secret information as a share. Shares that are not fixed in a given sharing are referred to as non-fixed shares.
U.S. patent application Ser. No. 14/962,606, filed Dec. 8, 2015, entitled “Proactivized Threshold Password-Based Secret Sharing with Flexible Key Rotation,” incorporated by reference herein, discloses a proactivization technique for threshold PBSS. In one or more embodiments, shares are being refreshed by a trusted entity (possibly one of the current share-holder devices). The trusted entity is responsible to choose the randomness that is needed to produce the random correction shares that are employed for producing the new refreshed sharing of the secret. Such a trusted entity may not be available, however, when a new sharing is needed.
Therefore, a need remains for distributed proactive techniques for PBSS that do not require the use of a centralized trusted entity during proactivization.